//-----------------NodeIndex

template<typename T>
NodeIndexFixed<T>::NodeIndexFixed()
{
	this->nextNodeIndex  = -1;

}
template<typename T>
NodeIndexFixed<T>::NodeIndexFixed(const T& val)
{
	this->value = val;
	this->nextNodeIndex  = -1;

}
template<typename T>
NodeIndexFixed<T>::NodeIndexFixed(const T& val, index_type next)
{
	this->value = val;
	this->nextNodeIndex  = next;

}
 //------------------ ITERATORS -------------------------------------
template<typename T>	
FixedList_Iterator_Forward<T>::FixedList_Iterator_Forward()
{
	this->list = NULL;
	this->currentNodeIndex = -1;

}
template<typename T>	
FixedList_Iterator_Forward<T>::FixedList_Iterator_Forward(const FixedList_Iterator_Forward & other)
{
	this->list = other.list;
	this->currentNodeIndex = other.currentNodeIndex;
}
template<typename T>	
FixedList_Iterator_Forward<T>::FixedList_Iterator_Forward( NodeIndexFixed<T>  *vec, int index)
{
	this->list = vec;
	this->currentNodeIndex = index;
}
template<typename T>
FixedList_Iterator_Forward<T>& FixedList_Iterator_Forward<T>::operator ++()
{
	this->currentNodeIndex = this->list[currentNodeIndex].nextNodeIndex;
	return *this;
}
template<typename T>
FixedList_Iterator_Forward<T> FixedList_Iterator_Forward<T>::operator ++(int)
{
	iterator_category copy(*this);
	this->operator++();
	return copy;
}

template<typename T>
bool operator ==(const FixedList_Iterator_Forward<T>& it1, const FixedList_Iterator_Forward<T>& it2)
{
	return (it1.list == it2.list && it1.currentNodeIndex == it2.currentNodeIndex)?true:false;
}
template<typename T>
bool operator !=(const FixedList_Iterator_Forward<T>& it1, const FixedList_Iterator_Forward<T>& it2)
{
	return !(it1 == it2);
}
template<typename T>
typename FixedList_Iterator_Forward<T>::reference  FixedList_Iterator_Forward<T>::operator *()
{
	return this->list[this->currentNodeIndex].value;
}

//------------------ CONST ITERATOR -------------------------------------
template<typename T>	
FixedList_Iterator_Forward_Const<T>::FixedList_Iterator_Forward_Const()
{
	this->list = NULL;
	this->currentNodeIndex = -1;

}
template<typename T>	
FixedList_Iterator_Forward_Const<T>::FixedList_Iterator_Forward_Const(const FixedList_Iterator_Forward_Const & other)
{
	this->list = other.list;
	this->currentNodeIndex = other.currentNodeIndex;
}
template<typename T>	
FixedList_Iterator_Forward_Const<T>::FixedList_Iterator_Forward_Const(NodeIndexFixed<T> *vec, int index)
{
	this->list = vec;
	this->currentNodeIndex = index;
}
template<typename T>
FixedList_Iterator_Forward_Const<T>& FixedList_Iterator_Forward_Const<T>::operator ++()
{
	this->currentNodeIndex = (*this->list)[currentNodeIndex].nextNodeIndex;
	return *this;
}
template<typename T>
FixedList_Iterator_Forward_Const<T> FixedList_Iterator_Forward_Const<T>::operator ++(int)
{
	iterator_category copy(*this);
	this->operator++();
	return copy;
}

template<typename T>
bool operator ==(const FixedList_Iterator_Forward_Const<T>& it1, const FixedList_Iterator_Forward_Const<T>& it2)
{
	return (it1.list == it2.list && it1.currentNodeIndex == it2.currentNodeIndex)?true:false;
}
template<typename T>
bool operator !=(const FixedList_Iterator_Forward_Const<T>& it1, const FixedList_Iterator_Forward_Const<T>& it2)
{
	return !(it1 == it2);
}
template<typename T>
typename FixedList_Iterator_Forward_Const<T>::reference  FixedList_Iterator_Forward_Const<T>::operator *()
{
	return (*this->list)[this->currentNodeIndex].value;
}

//--------------------- CONTAINER --------------------------------------------
template<typename T,int SIZE>
FixedList< T, SIZE>::FixedList()// ::FixedList(  )
{
	this->length = 0;
	this->freeListHead = this->head = this->tail = -1;
	clearFreeList();
}

template<typename T,int SIZE >
FixedList<T,SIZE>::~FixedList(  )
{
	
}
template<typename T,int SIZE >
FixedList<T,SIZE>& FixedList<T,SIZE>::operator =(const FixedList<T,SIZE>& other)
{
	//this->list = other.list;

	this->head = other.head;
	this->tail = other.tail;
	this->length = other.length;
	this->freeListHead = other.freeListHead;

	for (size_t i=0; i < SIZE; ++i)
	{
		this->list[i] = other.list[i];
	}
}
template<typename T,int SIZE >
void FixedList<T,SIZE>::assign( size_type count, const T& value )
{
	//TODO
}


/*----- ELEMENT ACCESS -------*/
template<typename T,int SIZE >
typename FixedList<T,SIZE>::reference FixedList<T,SIZE>::front()
{
	return this->list[head];
}

template<typename T,int SIZE >
typename FixedList<T,SIZE>::const_reference FixedList<T,SIZE>::front() const
{
	return this->list[head];
}

template<typename T,int SIZE >
typename FixedList<T,SIZE>::reference FixedList<T,SIZE>::back()
{
	return this->list[tail];
}

template<typename T,int SIZE >
typename FixedList<T,SIZE>::const_reference FixedList<T,SIZE>::back() const
{
	return this->list[tail];
}

/*----- ITERATORS -------*/

template<typename T,int SIZE >
typename FixedList<T,SIZE>::iterator FixedList<T,SIZE>::begin() 
{
	return iterator(list,this->head);
}

//TODO 
template<typename T,int SIZE >
typename FixedList<T,SIZE>::const_iterator FixedList<T,SIZE>::begin() const
{
	return const_iterator(this->list,this->head);
}

template<typename T,int SIZE >
typename FixedList<T,SIZE>::iterator FixedList<T,SIZE>::end()
{
	return iterator(this->list,-1);
}


/*------- CAPACITY ----------*/

template<typename T,int SIZE >
bool FixedList<T,SIZE>::empty() const
{
	return this->length ==0 ;
}
template<typename T,int SIZE >
typename FixedList<T,SIZE>::size_type FixedList<T,SIZE>::size() const
{
	return this->length;
}

template<typename T,int SIZE >
typename FixedList<T,SIZE>::size_type FixedList<T,SIZE>::max_size() const
{
	return SIZE;
}

/*------- MODIFIERS ----------*/

template<typename T,int SIZE >
void FixedList<T,SIZE>::clear()
{
	this->tail = this->head =-1;
	this->length = 0;
//	this->list.clear();
	clearFreeList();
}

template<typename T,int SIZE >
typename FixedList<T,SIZE>::iterator FixedList<T,SIZE>::insert( iterator pos, const T& value )
{
	if(pos.currentNodeIndex == head)
	{
		push_front(value);
		return begin();
	}
	if (pos == end()){
		push_back(value);
		return iterator(this->list, this->tail);
	}
	int prevIndex = prevNodeIndex(pos);
	int nextIndex = list[prevIndex].nextNodeIndex;

	int newIndex;
	if (freeListHead != -1){
		newIndex = popNodeFromFreeList();
		list[prevIndex].nextNodeIndex = newIndex;
		list[newIndex].value = value;
		list[newIndex].nextNodeIndex = nextIndex;
	}else{
		//TODO: 
		/*newIndex = this->list.size();
		this->list.push_back(NodeIndex<T>(value,nextIndex));
		list[prevIndex].nextNodeIndex = newIndex;*/
		
	}
	++this->length;
	return iterator(this->list, newIndex);
}

template<typename T,int SIZE >
void FixedList<T,SIZE>::insert( iterator pos, size_type count, const T& value )
{
	for (int i = 0 ; i < count; ++i){
		pos = insert(pos, value);	
	} 
}

//TODO: 
//template <class InputIterator>
//void insert( iterator pos, InputIterator first, InputIterator last);

template<typename T,int SIZE >
typename FixedList<T,SIZE>::iterator FixedList<T,SIZE>::erase( iterator pos )
{

	if (pos == begin()){
		pop_front();
		return begin();
	}else if(pos == iterator(this->list, this->tail))
	{
		pop_back();
		return end();
	}
	int prevIndex = prevNodeIndex(pos);
	int targetIndex = this->list[prevIndex].nextNodeIndex;
	int nextIndex = this->list[targetIndex].nextNodeIndex;
	
	addNodeToFreeList(targetIndex);
	this->list[prevIndex].nextNodeIndex = nextIndex;
	
	--this->length;

	return iterator(this->list, nextIndex);
}

template<typename T,int SIZE >
typename FixedList<T,SIZE>::iterator FixedList<T,SIZE>::erase( iterator first, iterator last )
{
	while(first != last && first != end()){
		first = erase(first);
	}
	if (first != end()){
		iterator next = first;
		++next;
		erase(first);
		return iterator(next);
	}
	return end();
}

template<typename T,int SIZE >
void FixedList<T,SIZE>::push_back( const T& value )
{
	
	if (freeListHead != -1){
		//recover space from freelist
		int newIndex = popNodeFromFreeList();
		if (tail != -1)
			this->list[tail].nextNodeIndex = newIndex;
		if (this->length == 0)
			head = newIndex;
		tail = newIndex;
		this->list[tail].value = value;
		this->list[tail].nextNodeIndex = -1;
	}else{
		/*int newIndex = this->length;
		this->list.push_back(NodeIndex<T>(value));

		if (this->length == 0){
			this->head = newIndex;
		}else{
			this->list[tail].nextNodeIndex = newIndex;
		}
		this->tail = newIndex;*/
	}
	
	++this->length;
}

template<typename T,int SIZE >
void FixedList<T,SIZE>::pop_back()
{
	int nodeBeforeTail = prevNodeIndex(tail);
	addNodeToFreeList(tail);
	this->list[nodeBeforeTail].nextNodeIndex = -1;
	tail = nodeBeforeTail;

	--this->length;
}

template<typename T,int SIZE >
void FixedList<T,SIZE>::push_front( const T& value )
{
	if (freeListHead != -1){
		//recover space from freelist
		int newIndex = popNodeFromFreeList();
		this->list[newIndex].nextNodeIndex = this->head;
		this->list[newIndex].value= value;
		this->head = newIndex;
	}else{
	/*	int newIndex = this->list.size();
		this->list.push_back(NodeIndex<T>(value, head));
		this->head = newIndex;*/
	}
	++this->length;
	

}

template<typename T,int SIZE >
void FixedList<T,SIZE>::pop_front()
{
	int nextIndex = this->list[head].nextNodeIndex;
	addNodeToFreeList(head);
	head = nextIndex;
	
	--this->length;
}

//--------------- PRIVATE INTERNALS ----------------------
template<typename T,int SIZE >
int FixedList<T,SIZE>::prevNodeIndex(int node)
{
	if (this->length <=1 )
			return -1;

	int prevIndex = -1;
	int curr = this->head;
	int next = list[curr].nextNodeIndex;
	while(next != -1)
	{
		if(next == node){
			return curr;
		}
		curr = next;
		next = list[next].nextNodeIndex;
	}
	return -1;
	
}
template<typename T,int SIZE >
int FixedList<T,SIZE>::prevNodeIndex(iterator node)
{
	if (this->length <=1 )
		return -1;

	iterator curr = ++begin();
	int prevIndex = head;

	while(curr != end()){
		if (curr == node){
			//found
			return prevIndex;
		}
		prevIndex =  this->list[prevIndex].nextNodeIndex;
		++curr;
	}
	return -1;	
}


template<typename T,int SIZE >
void FixedList<T,SIZE>::addNodeToFreeList(int nodeIndex)
{
	int prevHead = this->freeListHead;
	this->freeListHead = nodeIndex;
	this->list[freeListHead].nextNodeIndex = prevHead;
}
template<typename T,int SIZE >
int FixedList<T,SIZE>::popNodeFromFreeList()
{
	int prevHead = this->freeListHead;
	this->freeListHead = this->list[prevHead].nextNodeIndex;
	return prevHead;
}
template<typename T,int SIZE >
void FixedList<T,SIZE>::clearFreeList()
{
	for (size_t i= 0 ; i < SIZE -1; ++i){
		this->list[i].nextNodeIndex = i +1;
	}
	this->list[SIZE -1].nextNodeIndex = -1;
	this->head = this->tail = -1;
	this->freeListHead = 0;
}

